#include "stack_queue.h"
#include <vector>
#include <cctype>
#include <new>  
using namespace std;

listNode::listNode() : next(NULL), data(0) {}

listNode::listNode(int nodeData, listNode* succ) : next(succ), data(nodeData) {}

MyStack::MyStack() : topNode(NULL), stackSize(0) {}

MyStack::~MyStack() {
    int discardedValue;
    while (pop(discardedValue)) {}  
}

bool MyStack::push(const int& value) {
    listNode* newNode = new(nothrow) listNode(value, topNode);
    if (newNode == NULL) return false;
    topNode = newNode;
    ++stackSize;
    return true;
}

bool MyStack::pop(int& item) {
    if (topNode == NULL) return false;  
    item = topNode->data;
    listNode* oldTop = topNode;
    topNode = topNode->next;
    delete oldTop;  
    --stackSize;
    return true;
}

bool MyStack::getTop(int& item) {
    if (topNode == NULL) return false;
    item = topNode->data;  
    return true;
}

void MyStack::printStack() {
    listNode* p = topNode;
    while (p != NULL) {
        if (p->next == NULL)
            cout << p->data << endl;
        else
            cout << p->data << ",";
        p = p->next;
    }
}
MyQueue::MyQueue(const int& cap) : queue(NULL), capacity(cap), front(0), rear(0) {
    if (capacity < 2) {
        capacity = 2;  
    }
    queue = new int[capacity];  
}

MyQueue::~MyQueue() {
    delete[] queue; 
    queue = NULL;
}

bool MyQueue::isFull() {
    return ((rear + 1) % capacity) == front;
}

bool MyQueue::enQueue(const int& value) {
    if (isFull()) return false;  
    queue[rear] = value;
    rear = (rear + 1) % capacity;  
    return true;
}

bool MyQueue::deQueue(int& item) {
    if (front == rear) return false;  
    item = queue[front];
    front = (front + 1) % capacity; 
    return true;
}

bool MyQueue::getFront(int& item) {
    if (front == rear) return false;  
    item = queue[front]; 
    return true;
}

void MyQueue::printQueue() {
    int cursor = front;
    while (cursor != rear) {
        if ((cursor + 1) % capacity == rear)
            cout << queue[cursor] << endl;
        else
            cout << queue[cursor] << ",";
        cursor = (cursor + 1) % capacity;
    }
}

static int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

static bool isOperator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

bool postfixExpression(const string& expr, string& result) {
    result.clear();
    MyStack opStack;  
    auto pushOp = [&](char c) -> bool { int v = static_cast<int>(c); return opStack.push(v); };
    auto popOp = [&](char& c) -> bool { int v; if (!opStack.pop(v)) return false; c = static_cast<char>(v); return true; };
    auto topOp = [&](char& c) -> bool { int v; if (!opStack.getTop(v)) return false; c = static_cast<char>(v); return true; };

    bool expectOperand = true;  
    for (size_t i = 0; i < expr.size(); ++i) {
        char ch = expr[i];
        if (isspace(static_cast<unsigned char>(ch))) continue;  

        if (isdigit(static_cast<unsigned char>(ch))) {
            if (!expectOperand) { result = "Expression is wrong!"; return false; }
            result.push_back(ch);
            expectOperand = false;
        }
        else if (ch == '(') {
            if (!expectOperand) { result = "Expression is wrong!"; return false; }
            if (!pushOp(ch)) { result = "Expression is wrong!"; return false; }
            expectOperand = true;
        }
        else if (ch == ')') {
            if (expectOperand) { result = "Expression is wrong!"; return false; }
            char top;
            bool foundLeftParen = false;
            while (topOp(top)) {
                if (top == '(') { int dummy; opStack.pop(dummy); foundLeftParen = true; break; }
                char op; popOp(op); result.push_back(op);
            }
            if (!foundLeftParen) { result = "Expression is wrong!"; return false; } 
            expectOperand = false;
        }
        else if (isOperator(ch)) {
            if (expectOperand) { result = "Expression is wrong!"; return false; }
            char top;
            while (topOp(top) && top != '(' && precedence(top) >= precedence(ch)) {
                char op; popOp(op); result.push_back(op);
            }
            if (!pushOp(ch)) { result = "Expression is wrong!"; return false; }
            expectOperand = true;
        }
        else {
            result = "Expression is wrong!";
            return false;
        }
    }
    if (expectOperand) { result = "Expression is wrong!"; return false; }
    char top;
    while (topOp(top)) {
        if (top == '(') { result = "Expression is wrong!"; return false; }  
        char op; popOp(op); result.push_back(op);
    }
    return true;
}


bool expressionVal(const string& expr, int& result) {
    result = 0;
    string post;
    if (!postfixExpression(expr, post)) {
        result = 0;
        return false; 
    }

    MyStack valueStack;  
    for (char ch : post) {
        if (isdigit(static_cast<unsigned char>(ch))) {
            int v = ch - '0';
            if (!valueStack.push(v)) { result = 0; return false; }
        }
        else if (isOperator(ch)) {
            int rhs, lhs;
            if (!valueStack.pop(rhs) || !valueStack.pop(lhs)) { result = 0; return false; }  
            int calc = 0;
            if (ch == '+') calc = lhs + rhs;
            else if (ch == '-') calc = lhs - rhs;
            else if (ch == '*') calc = lhs * rhs;
            else if (ch == '/') {
                if (rhs == 0) { result = 0; return false; } 
                calc = lhs / rhs;  
            }
            if (!valueStack.push(calc)) { result = 0; return false; }
        }
        else {
            result = 0;
            return false; 
        }
    }
    int finalVal;
    if (!valueStack.pop(finalVal)) { result = 0; return false; }
    int leftover;
    if (valueStack.pop(leftover)) { result = 0; return false; }  
    result = finalVal;
    return true;
}
void yanghui(const int& n) {
    if (n <= 0) return;  

    vector<int> currentRow;
    currentRow.push_back(1);
    currentRow.push_back(1);  

    for (int i = 1; i <= n; ++i) {
        MyQueue rowQueue(static_cast<int>(currentRow.size()) + 2);
        for (size_t k = 0; k < currentRow.size(); ++k) {
            rowQueue.enQueue(currentRow[k]);
        }
        rowQueue.printQueue();  
        vector<int> nextRow;
        nextRow.reserve(currentRow.size() + 1);
        nextRow.push_back(1);
        for (size_t j = 1; j < currentRow.size(); ++j) {
            nextRow.push_back(currentRow[j - 1] + currentRow[j]);
        }
        nextRow.push_back(1);
        currentRow.swap(nextRow); 
    }
}